import java.util.*;
public class test {
    // leetcode 62.不同路径(记忆化搜索)
    class Solution {
        public int[][] memo = new int[101][101];
        public int uniquePaths(int m, int n) {
            memo[0][0] = 1;
            return dfs(m - 1,n - 1);
        }
        public int dfs(int m,int n){
            if(m < 0 || n < 0){
                return 0;
            }
            if(memo[m][n] != 0){
                return memo[m][n];
            }
            memo[m][n] = dfs(m - 1,n) + dfs(m,n - 1);
            return memo[m][n];
        }
    }
    // leetcode 63.不同路径Ⅱ(记忆化搜索)
    class Solution {
        public int[][] nums = new int[102][102];
        public int[][] obstacleGrid;
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            this.obstacleGrid = obstacleGrid;
            nums[1][1] = 1;
            return dfs(obstacleGrid.length ,obstacleGrid[0].length);
        }
        public int dfs(int m,int n){
            if(m < 1 || n < 1){
                return 0;
            }
            if(obstacleGrid[m - 1][n - 1] == 1){
                return 0;
            }
            if(nums[m][n] != 0){
                return nums[m][n];
            }
            nums[m][n] = dfs(m - 1,n) + dfs(m,n - 1);
            return nums[m][n];
        }
    }
    // leetcode 300.最长递增子序列(记忆化搜索)
    class Solution {
        // 记忆化搜索
        public int[] memo;
        public int[] nums;
        public int lengthOfLIS1(int[] nums) {
            int n = nums.length;
            memo = new int[n];
            this.nums = nums;
            int ret = 1;
            for(int i = 0;i < n;i++){
                ret = Math.max(ret,dfs(i));
            }
            return ret;
        }
        public int dfs(int m){
            if(memo[m] != 0){
                return memo[m];
            }
            int ret = 1;
            for(int i = m + 1;i < nums.length;i++){
                if(nums[i] > nums[m]){
                    memo[i] = dfs(i);
                    ret = Math.max(ret,memo[i] + 1);
                }
            }
            memo[m] = ret;
            return ret;
        }
        // 动态规划
        public int lengthOfLIS(int[] nums) {
            // 1. 创建dp表
            int n = nums.length;
            int[] dp = new int[n];
            // 2. 初始化
            Arrays.fill(dp,1);
            // 3. 填表
            int max = 1;
            for(int i = n - 1;i >= 0;i--){
                for(int j = i;j < n;j++){
                    if(nums[j] > nums[i]){
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                    }
                }
                max = Math.max(max,dp[i]);
            }
            // 4. 返回值
            return max;
        }
    }
}
